public class Reverse_nodes_in_k_group {
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
            ListNode dummyHead=new ListNode(-1);
            dummyHead.next=head;
            ListNode pre=dummyHead;
            ListNode end=dummyHead;
            while(end.next!=null){
                //如果节点总数不是 k 的整数倍，最后剩余的节点保持原有顺序
                for(int i=0;i<k&&end!=null;i++) end=end.next;
                if(end==null)break;
                //定位反转节点
                ListNode start=pre.next;
                ListNode nextTurn=end.next;
                //断开链接
                end.next=null;
                //反转
                pre.next=reverse(start);
                // 接回到原来的链表中
                start.next=nextTurn;
                //下一轮循环
                pre=start;
                end=pre;
            }
            return dummyHead.next;
        }

        ListNode  reverse(ListNode head){
            if(head.next==null) return head;
            ListNode node= reverse(head.next);
            head.next.next=head;
            head.next=null;
            return node;
        }
    }


}
